home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / lib / c / stdlib / RCS / qsort.c,v < prev    next >
Encoding:
Text File  |  1989-03-22  |  10.5 KB  |  336 lines
  1. head     1.5;
  2. branch   ;
  3. access   ;
  4. symbols  ;
  5. locks    ; strict;
  6. comment  @ * @;
  7.  
  8.  
  9. 1.5
  10. date     89.03.22.00.47.21;  author rab;  state Exp;
  11. branches ;
  12. next     1.4;
  13.  
  14. 1.4
  15. date     88.08.29.08.54.58;  author ouster;  state Exp;
  16. branches ;
  17. next     1.3;
  18.  
  19. 1.3
  20. date     88.05.25.13.44.41;  author ouster;  state Exp;
  21. branches ;
  22. next     1.2;
  23.  
  24. 1.2
  25. date     88.05.23.08.38.56;  author ouster;  state Exp;
  26. branches ;
  27. next     1.1;
  28.  
  29. 1.1
  30. date     88.05.21.14.46.03;  author ouster;  state Exp;
  31. branches ;
  32. next     ;
  33.  
  34.  
  35. desc
  36. @@
  37.  
  38.  
  39. 1.5
  40. log
  41. @*** empty log message ***
  42. @
  43. text
  44. @/* 
  45.  * qsort.c --
  46.  *
  47.  *    Source code for the library routine "qsort".  Taken
  48.  *    from BSD.
  49.  *
  50.  * Copyright 1988 Regents of the University of California
  51.  * Permission to use, copy, modify, and distribute this
  52.  * software and its documentation for any purpose and without
  53.  * fee is hereby granted, provided that the above copyright
  54.  * notice appear in all copies.  The University of California
  55.  * makes no representations about the suitability of this
  56.  * software for any purpose.  It is provided "as is" without
  57.  * express or implied warranty.
  58.  */
  59.  
  60. #ifndef lint
  61. static char rcsid[] = "$Header: /sprite/src/lib/c/stdlib/RCS/qsort.c,v 1.4 88/08/29 08:54:58 ouster Exp Locker: rab $ SPRITE (Berkeley)";
  62. #endif /* not lint */
  63.  
  64. #include <stdlib.h>
  65.  
  66. /*
  67.  * qsort.c:
  68.  * Our own version of the system qsort routine which is faster by an average
  69.  * of 25%, with lows and highs of 10% and 50%.
  70.  * The THRESHold below is the insertion sort threshold, and has been adjusted
  71.  * for records of size 48 bytes.
  72.  * The MTHREShold is where we stop finding a better median.
  73.  */
  74.  
  75. #define         THRESH          4               /* threshold for insertion */
  76. #define         MTHRESH         6               /* threshold for median */
  77.  
  78. static  int             (*qcmp)();              /* the comparison routine */
  79. static  int             qsz;                    /* size of each record */
  80. static  int             thresh;                 /* THRESHold in chars */
  81. static  int             mthresh;                /* MTHRESHold in chars */
  82. static  void            qst();
  83. /*
  84.  * qsort:
  85.  * First, set up some global parameters for qst to share.  Then, quicksort
  86.  * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
  87.  * It's not...
  88.  */
  89.  
  90. void
  91. qsort(base, n, size, compar)
  92.         char    *base;
  93.         int     n;
  94.         int     size;
  95.         int     (*compar)();
  96. {
  97.         register char c, *i, *j, *lo, *hi;
  98.         char *min, *max;
  99.  
  100.         if (n <= 1)
  101.                 return;
  102.         qsz = size;
  103.         qcmp = compar;
  104.         thresh = qsz * THRESH;
  105.         mthresh = qsz * MTHRESH;
  106.         max = base + n * qsz;
  107.         if (n >= THRESH) {
  108.                 qst(base, max);
  109.                 hi = base + thresh;
  110.         } else {
  111.                 hi = max;
  112.         }
  113.         /*
  114.          * First put smallest element, which must be in the first THRESH, in
  115.          * the first position as a sentinel.  This is done just by searching
  116.          * the first THRESH elements (or the first n if n < THRESH), finding
  117.          * the min, and swapping it into the first position.
  118.          */
  119.         for (j = lo = base; (lo += qsz) < hi; )
  120.                 if (qcmp(j, lo) > 0)
  121.                         j = lo;
  122.         if (j != base) {
  123.                 /* swap j into place */
  124.                 for (i = base, hi = base + qsz; i < hi; ) {
  125.                         c = *j;
  126.                         *j++ = *i;
  127.                         *i++ = c;
  128.                 }
  129.         }
  130.         /*
  131.          * With our sentinel in place, we now run the following hyper-fast
  132.          * insertion sort.  For each remaining element, min, from [1] to [n-1],
  133.          * set hi to the index of the element AFTER which this one goes.
  134.          * Then, do the standard insertion sort shift on a character at a time
  135.          * basis for each element in the frob.
  136.          */
  137.         for (min = base; (hi = min += qsz) < max; ) {
  138.                 while (qcmp(hi -= qsz, min) > 0)
  139.                         /* void */;
  140.                 if ((hi += qsz) != min) {
  141.                         for (lo = min + qsz; --lo >= min; ) {
  142.                                 c = *lo;
  143.                                 for (i = j = lo; (j -= qsz) >= hi; i = j)
  144.                                         *i = *j;
  145.                                 *i = c;
  146.                         }
  147.                 }
  148.         }
  149. }
  150.  
  151. /*
  152.  * qst:
  153.  * Do a quicksort
  154.  * First, find the median element, and put that one in the first place as the
  155.  * discriminator.  (This "median" is just the median of the first, last and
  156.  * middle elements).  (Using this median instead of the first element is a big
  157.  * win).  Then, the usual partitioning/swapping, followed by moving the
  158.  * discriminator into the right place.  Then, figure out the sizes of the two
  159.  * partions, do the smaller one recursively and the larger one via a repeat of
  160.  * this code.  Stopping when there are less than THRESH elements in a partition
  161.  * and cleaning up with an insertion sort (in our caller) is a huge win.
  162.  * All data swaps are done in-line, which is space-losing but time-saving.
  163.  * (And there are only three places where this is done).
  164.  */
  165.  
  166. static void
  167. qst(base, max)
  168.         char *base, *max;
  169. {
  170.         register char c, *i, *j, *jj;
  171.         register int ii;
  172.         char *mid, *tmp;
  173.         int lo, hi;
  174.  
  175.         /*
  176.          * At the top here, lo is the number of characters of elements in the
  177.          * current partition.  (Which should be max - base).
  178.          * Find the median of the first, last, and middle element and make
  179.          * that the middle element.  Set j to largest of first and middle.
  180.          * If max is larger than that guy, then it's that guy, else compare
  181.          * max with loser of first and take larger.  Things are set up to
  182.          * prefer the middle, then the first in case of ties.
  183.          */
  184.         lo = max - base;                /* number of elements as chars */
  185.         do      {
  186.                 mid = i = base + qsz * ((lo / qsz) >> 1);
  187.                 if (lo >= mthresh) {
  188.                         j = (qcmp((jj = base), i) > 0 ? jj : i);
  189.                         if (qcmp(j, (tmp = max - qsz)) > 0) {
  190.                                 /* switch to first loser */
  191.                                 j = (j == jj ? i : jj);
  192.                                 if (qcmp(j, tmp) < 0)
  193.                                         j = tmp;
  194.                         }
  195.                         if (j != i) {
  196.                                 ii = qsz;
  197.                                 do      {
  198.                                         c = *i;
  199.                                         *i++ = *j;
  200.                                         *j++ = c;
  201.                                 } while (--ii);
  202.                         }
  203.                 }
  204.                 /*
  205.                  * Semi-standard quicksort partitioning/swapping
  206.                  */
  207.                 for (i = base, j = max - qsz; ; ) {
  208.                         while (i < mid && qcmp(i, mid) <= 0)
  209.                                 i += qsz;
  210.                         while (j > mid) {
  211.                                 if (qcmp(mid, j) <= 0) {
  212.                                         j -= qsz;
  213.                                         continue;
  214.                                 }
  215.                                 tmp = i + qsz;  /* value of i after swap */
  216.                                 if (i == mid) {
  217.                                         /* j <-> mid, new mid is j */
  218.                                         mid = jj = j;
  219.                                 } else {
  220.                                         /* i <-> j */
  221.                                         jj = j;
  222.                                         j -= qsz;
  223.                                 }
  224.                                 goto swap;
  225.                         }
  226.                         if (i == mid) {
  227.                                 break;
  228.                         } else {
  229.                                 /* i <-> mid, new mid is i */
  230.                                 jj = mid;
  231.                                 tmp = mid = i;  /* value of i after swap */
  232.                                 j -= qsz;
  233.                         }
  234.                 swap:
  235.                         ii = qsz;
  236.                         do      {
  237.                                 c = *i;
  238.                                 *i++ = *jj;
  239.                                 *jj++ = c;
  240.                         } while (--ii);
  241.                         i = tmp;
  242.                 }
  243.                 /*
  244.                  * Look at sizes of the two partitions, do the smaller
  245.                  * one first by recursion, then do the larger one by
  246.                  * making sure lo is its size, base and max are update
  247.                  * correctly, and branching back.  But only repeat
  248.                  * (recursively or by branching) if the partition is
  249.                  * of at least size THRESH.
  250.                  */
  251.                 i = (j = mid) + qsz;
  252.                 if ((lo = j - base) <= (hi = max - i)) {
  253.                         if (lo >= thresh)
  254.                                 qst(base, j);
  255.                         base = i;
  256.                         lo = hi;
  257.                 } else {
  258.                         if (hi >= thresh)
  259.                                 qst(i, max);
  260.                         max = j;
  261.                 }
  262.         } while (lo >= thresh);
  263. }
  264. @
  265.  
  266.  
  267. 1.4
  268. log
  269. @Change type from void to none.
  270. @
  271. text
  272. @d18 2
  273. a19 2
  274. static char rcsid[] = "$Header: qsort.c,v 1.3 88/05/25 13:44:41 ouster Exp $ SPRITE (Berkeley)";
  275. #endif not lint
  276. d21 2
  277. d39 1
  278. a39 1
  279.  
  280. d47 1
  281. d123 1
  282. a123 1
  283. static
  284. @
  285.  
  286.  
  287. 1.3
  288. log
  289. @It's free code after all.  Change copyright notice again.
  290. @
  291. text
  292. @d18 1
  293. a18 1
  294. static char rcsid[] = "$Header: qsort.c,v 1.2 88/05/23 08:38:56 ouster Exp $ SPRITE (Berkeley)";
  295. a44 1
  296. void
  297. @
  298.  
  299.  
  300. 1.2
  301. log
  302. @Change copyright notice.
  303. @
  304. text
  305. @d7 8
  306. a14 4
  307.  * Copyright (c) 1980 Regents of the University of California.
  308.  * All rights reserved.  The Berkeley software License Agreement
  309.  * specifies the terms and conditions for redistribution.
  310.  * This code may have AT&T roots and cannot be distributed freely.
  311. d18 1
  312. a18 1
  313. static char rcsid[] = "$Header: qsort.c,v 1.1 88/05/21 14:46:03 ouster Exp $ SPRITE (Berkeley)";
  314. @
  315.  
  316.  
  317. 1.1
  318. log
  319. @Initial revision
  320. @
  321. text
  322. @d7 4
  323. a10 8
  324.  * Copyright 1988 Regents of the University of California
  325.  * Permission to use, copy, modify, and distribute this
  326.  * software and its documentation for any purpose and without
  327.  * fee is hereby granted, provided that the above copyright
  328.  * notice appear in all copies.  The University of California
  329.  * makes no representations about the suitability of this
  330.  * software for any purpose.  It is provided "as is" without
  331.  * express or implied warranty.
  332. d14 1
  333. a14 1
  334. static char rcsid[] = "$Header: proto.c,v 1.2 88/03/11 08:39:08 ouster Exp $ SPRITE (Berkeley)";
  335. @
  336.